﻿using System;

namespace EncryptX
{
    public class VeryLong
    {
        #region Fields

        const int nMax = 10000;//MAx of n (look below)
        const int bse = 10000;//num of digits in each section is 4
        const int bseDigits = 4;//num of digits in each section is 4

        int sgn = 1;//1 or -1;
        int ndgts;//Num of bse-digit slots
        int[] arr;

        #endregion

        #region Methods

        public VeryLong()//zero
        {
            sgn = 1;
            ndgts = 1;
            arr = new int[1];
            arr[0] = 0;
        }

        public VeryLong(VeryLong l1)//Copy
        {
            sgn = l1.sgn;
            ndgts = l1.ndgts;
            arr = new int[ndgts];
            for (int i = 0; i < ndgts; i++)
                arr[i] = l1.arr[i];
        }

        public VeryLong(int fromint)//New VeryLong=_base
        {
            int inttmp;
            if (fromint < 0) { sgn = -1; inttmp = (-1) * fromint; }
            else { sgn = 1; inttmp = fromint; }
            ndgts = (getDigitsNum(inttmp) - 1) / bseDigits + 1;
            arr = new int[ndgts];
            int i = 0;
            do
            {
                arr[i] = inttmp % bse;
                inttmp /= bse;
                i++;
            }
            while (inttmp > 0);
            if (ndgts != i) throw new Exception(String.Format("Error converting int {0} to VeryLong", fromint));
        }

        int getDigitsNum(int intgr)
        {
            int i = 0;
            int itmp = Math.Abs(intgr);
            do
            {
                i++;
                itmp /= 10;
            } while (itmp > 0);
            return i;
        }

        public VeryLong(string s)//from string
        {
            string ts = s.Trim();
            if (ts[0] == '+') ts = ts.Remove(0, 1);
            if (ts[0] == '-') { sgn = -1; ts = ts.Remove(0, 1); }
            else { sgn = 1; }
            int l = ts.Length;
            ndgts = (l - 1) / bseDigits + 1;
            arr = new int[ndgts];
            //proc
            for (int i = 0; i < ndgts - 1; i++)
                arr[i] = int.Parse(ts.Substring(l - bseDigits * (i + 1), bseDigits));
            int dgtsLeft = l % bseDigits;//digits left to read from left or if ==0 that's left to do is to read last segment of nums
            if (dgtsLeft > 0)
                arr[ndgts - 1] = int.Parse(ts.Substring(0, dgtsLeft));
            else
                arr[ndgts - 1] = int.Parse(ts.Substring(0, bseDigits));
        }

        public override string ToString()
        {
            string s = "";
            string formatStr = String.Format("D{0}", bseDigits);
            if (ndgts > 0)
            {

                for (int i = 0; i < ndgts - 1; i++)
                    s = arr[i].ToString(formatStr) + s;
                s = arr[ndgts - 1].ToString() + s;
                if (sgn == -1) s = "-" + s;
            }
            else { s = "Not initialized"; }
            return s;
        }

        public string getInfo()
        {
            return String.Format("BaseDigits(slots): {0};\nValue: {1};", ndgts, this.ToString());
        }

        public static VeryLong add2PositiveVeryLongs(VeryLong l1, VeryLong l2)
        {
            if (l1.sgn == 1 && l2.sgn == 1)
            {
                VeryLong c=new VeryLong();
                int i, k;
                k = (l1.ndgts > l2.ndgts) ? l1.ndgts : l2.ndgts;
                c.arr = new int[k + 1];
                for (i = 0; i < k; i++)
                {
                    c.arr[i + 1] = (c.Arr(i) + l1.Arr(i) + l2.Arr(i)) / bse;
                    c.arr[i] = (c.Arr(i) + l1.Arr(i) + l2.Arr(i)) % bse;
                }
                c.ndgts = (c.arr[k] == 0) ? k : k + 1;
                return c;
            }
            else throw new Exception("add2PositiveVeryLongs Error: 2 Very Longs must be both positive");
        }        

        public static VeryLong sub2PosvLong(VeryLong l1, VeryLong l2, int shft)//Substracts 2 positive VLong with shift
        {
            if (l1.sgn == 1 && l2.sgn == 1)
            {
                VeryLong c = new VeryLong(l1);
                int i, j;
                for (i = 0; i < l2.ndgts; i++)
                {
                    c.arr[i + shft] -= l2.arr[i];
                    j = i;
                    while (c.arr[j + shft] < 0 && j < c.ndgts)
                    {
                        c.arr[j + shft] += bse;
                        c.arr[j + shft + 1]--;
                        j++;
                    }
                }
                i = c.ndgts - 1;
                while (i > 0 && c.arr[i] == 0)
                    i--;
                c.ndgts = i + 1;
                return c;
            }
            else throw new Exception("VeryLong.sub2PosvLong: 2 Very Longs must be both positive");
        }

        public VeryLong subByVLongSP(VeryLong l2, int shft)//Substract positive VLong by positive VLong with shift
        {
            if (this.sgn == 1 && l2.sgn == 1)
            {
                //VeryLong c = new VeryLong(l1);
                int i, j;
                for (i = 0; i < l2.ndgts; i++)
                {
                    this.arr[i + shft] -= l2.arr[i];
                    j = i;
                    while (this.arr[j + shft] < 0 && j < this.ndgts)
                    {
                        this.arr[j + shft] += bse;
                        this.arr[j + shft + 1]--;
                        j++;
                    }
                }
                i = this.ndgts - 1;
                while (i > 0 && this.arr[i] == 0)
                    i--;
                this.ndgts = i + 1;
                return this;
            }
            else throw new Exception("VeryLong.subByVLongSP: 2 Very Longs must be both positive");
        }    

        public int Arr(int idx)
        {
            if (idx >= 0)
            {
                if (idx < ndgts) return arr[idx];
                else return 0;
            }
            else throw new IndexOutOfRangeException("Arr(idx) must have positive or zero index");
        }

        //Result: -1 if l1<l2, 0 if equal, 1 if l1>l2; shift - shift digits left for l2 (l2<--(sift) digits)
        public static int compareTwo(VeryLong l1, VeryLong l2, int shift)//works only for shift - num of Base digits, not decimal
        {
            if (l1.isPositiveOrZero && l2.isPositiveOrZero)
            {
                if (l1.ndgts > l2.ndgts + shift) return 1;
                else if (l1.ndgts < l2.ndgts + shift) return -1;
                else
                {
                    int i = l1.ndgts - 1;
                    while (i >= shift && l1.arr[i] == l2.arr[i - shift])
                        i--;
                    if (i == shift - 1)
                    {
                        //Nums equal with shift for
                        for (i = 0; i < shift; i++)
                            if (l1.arr[i] > 0) return 1;
                        return 0;//Nums equal, "tail" of l1 is 0
                    }
                    else return (l1.arr[i] < l2.arr[i - shift]) ? (-1) : (1);
                }
            }
            else throw new NotImplementedException("VeryLong.compareTwo for positive VL only");
        }



        public static VeryLong vlongDivvlong(VeryLong l1, VeryLong l2, out VeryLong rem)//rem - remainder, returns quotient
        {
            switch (compareTwo(l1, l2, 0))
            {
                case -1://l1<l2
                    rem = new VeryLong(l1);
                    return new VeryLong(0);
                    //break;
                case 0://l1==l2
                    rem = new VeryLong(0);
                    return new VeryLong(1);
                    //break;
                case 1://l1>l2
                    VeryLong res=vlongDivvlongBasic(l1, l2, out rem);
                    return res;
                default:
                    throw new Exception("VeryLong.vlongDivvlong failed because VeryLong.compareTwo gave bad result");
            }
        }

        public static VeryLong vlongDivvlongBasic(VeryLong l1, VeryLong l2, out VeryLong rem)//result - quotient
        {
            VeryLong res = new VeryLong(0);
            int sp;
            rem = new VeryLong(l1);
            sp = l1.ndgts - l2.ndgts;
            if (compareTwo(l1, l2, sp) == -1)
                sp--;//l2*bse>l1
            res.ndgts = sp + 1;
            res.arr=new int[res.ndgts];
            while (sp >= 0)//look for next cyfer of result
            {
                res.arr[sp] = findBin(ref rem, l2, sp);
                sp--;
            }
            return res;
            //throw new NotImplementedException();
        }

        private static int findBin(ref VeryLong rem, VeryLong b, int sp)
        {
            int down = 0,
                up = bse;
            VeryLong c;
            while (up - 1 > down)
            {
                c = b * ((up + down) / 2);
                switch (compareTwo(rem, c, sp))
                {
                    case -1://l1<l2
                        up = (up + down) / 2;
                        break;
                    case 0://l1==l2
                        up = (up + down) / 2;
                        down = up;
                        break;
                    case 1://l1>l2
                        down = (up + down) / 2;
                        break;
                    default:
                        throw new Exception("VeryLong.findBin failed because VeryLong.compareTwo gave bad result");
                }
            }
            c = b * ((up + down) / 2);
            if (compareTwo(rem, c, 0) == 1)
                //rem = sub2PosvLong(rem, c, sp);//find reminder
                rem.subByVLongSP(c, sp);
            else
            {
                //c = sub2PosvLong(c, rem, sp);
                c.subByVLongSP(rem, sp);
                rem = c;
            }
            return (up + down) / 2;
        }

        public VeryLong pow(int p)
        {
            VeryLong c = new VeryLong(1);
            for (int i = 0; i < p; i++)
                c = c * this;
            return c;
        }

        public VeryLong powMod(VeryLong p, VeryLong n)//This method powers VLong to power p by modulo n using binary algorithm
        {
            VeryLong b = new VeryLong(1);
            if (n.isZero) return b;
            else
            {
                //VeryLong tp = p;
                if (p >= n)//Decrease power by Olsen theorem
                {
                    throw new NotImplementedException(":(");
                }
                VeryLong a = new VeryLong(this);
                VeryLong vl2 = new VeryLong(2);
                VeryLong q, r;//quotient and reminder
                q = vlongDivvlong(p, vl2, out r);
                if (r.isOne)//if p_bin[0]==1
                    b = new VeryLong(this);
                p = q;
                while (!p.isZero)
                {
                    a = (a * a) % n;
                    q = vlongDivvlong(p, vl2, out r);
                    if (r.isOne)
                        b = (a*b) % n;//if p_bin[1,2]==1
                    p = q;
                }

                return b;
            }
        }

        public bool isZero
        {
            get { return (ndgts == 1 && arr[0] == 0); }
        }

        public bool isOne
        {
            get { return (ndgts == 1 && arr[0] == 1); }
        }

        public bool isPositiveOrZero
        {
            get { return (sgn == 1); }
        }

        public bool isPositiveNonZero
        {
            get { return (!this.isZero && sgn == 1); }
        }

        #endregion

        #region Operators

        public static bool operator ==(VeryLong l1, VeryLong l2)
        {
            if (l1.sgn != l2.sgn) return false;
            if (l1.ndgts != l2.ndgts)
                return false;
            else
            {
                for (int i = 0; i < l1.ndgts; i++)
                    if (l1.arr[i] != l2.arr[i])
                        return false;
            }
            return true;
        }

        public static bool operator !=(VeryLong l1, VeryLong l2)
        {            
            return !(l1==l2);
        }

        public static bool operator >(VeryLong l1, VeryLong l2)
        {
            if (l1.sgn < l2.sgn) return false;
            else if (l1.sgn > l2.sgn) return true;
            else//if signs equal
                if (l1.ndgts < l2.ndgts) return (l1.sgn != 1);//false if l1.sgn==l2.sgn==1(+), true if else
                else
                    if (l1.ndgts > l2.ndgts) return (l1.sgn == 1);
                    else
                    {
                        int i = l1.ndgts-1;
                        while (i >= 0 && l1.arr[i] == l2.arr[i])
                            i--;
                        if (i == -1)
                            return false;
                        else
                            return (l1.sgn == 1) ? (l1.arr[i] > l2.arr[i]) : (l1.arr[i] < l2.arr[i]);
                    }
        }

        public static bool operator <(VeryLong l1, VeryLong l2)
        {
            if (l1.sgn > l2.sgn) return false;
            else if (l1.sgn < l2.sgn) return true;
            else//if signs equal
                if (l1.ndgts > l2.ndgts) return (l1.sgn != 1);
                else
                    if (l1.ndgts < l2.ndgts) return (l1.sgn == 1);
                    else
                    {
                        int i = l1.ndgts-1;
                        while (i >= 0 && l1.arr[i] == l2.arr[i])
                            i--;
                        if (i == -1)
                            return false;
                        else
                            return (l1.sgn == 1) ? (l1.arr[i] < l2.arr[i]) : (l1.arr[i] > l2.arr[i]);
                    }
        }

        public static bool operator <=(VeryLong l1, VeryLong l2)
        {return !(l1 > l2);}
        public static bool operator >=(VeryLong l1, VeryLong l2)
        { return !(l1 < l2); }

        public static VeryLong operator +(VeryLong l1, VeryLong l2)
        {
            if (l1.isPositiveOrZero && l2.isPositiveOrZero) return add2PositiveVeryLongs(l1, l2);
            else throw new NotImplementedException("Operator (+) only for 2 positive VeryLongs");
        }

        public static VeryLong operator -(VeryLong l1, VeryLong l2)
        {
            if (l1.isPositiveOrZero && l2.isPositiveOrZero)
            {
                if (l1 > l2) return sub2PosvLong(l1, l2, 0);
                else
                {
                    VeryLong res=sub2PosvLong(l2, l1, 0);
                    res.sgn=-1;
                    return res;
                }
            }
            else
                throw new NotImplementedException("Operator (-) only for positive numbers");
        }

        public static VeryLong operator *(VeryLong l1, VeryLong l2)
        {            
            int i, j, dv;
            VeryLong c=new VeryLong();
            c.arr = new int[l1.ndgts+l2.ndgts];
            for (i = 0; i < l1.ndgts; i++)
                for (j = 0; j < l2.ndgts; j++)
                {
                    dv = l1.arr[i] * l2.arr[j] + c.arr[i + j];
                    c.arr[i + j + 1] += dv / bse;
                    c.arr[i + j] = dv % bse;
                }
            c.ndgts = l1.ndgts + l2.ndgts;
            while (c.ndgts > 1 && c.arr[c.ndgts - 1] == 0)
                c.ndgts--;
            c.sgn = l1.sgn * l2.sgn;
            return c;
        }

        public static VeryLong operator *(VeryLong l, int k)
        {
            VeryLong c = new VeryLong();//zero            
            if (!(k == 0) && !l.isZero)             
            {
                c.arr = new int[l.ndgts + 1];
                int i;
                for (i = 0; i < l.ndgts; i++)
                {
                    c.arr[i + 1] = (l.arr[i] * k + c.arr[i]) / bse;
                    c.arr[i] = (l.arr[i] * k + c.arr[i]) % bse;
                }
                if (c.arr[l.ndgts] > 0)
                    c.ndgts = l.ndgts + 1;
                else
                    c.ndgts = l.ndgts;
            }
            c.sgn = l.sgn * ((k<0)?(-1):(1));            
            return c;
        }

        public static VeryLong operator /(VeryLong l1, VeryLong l2)
        {
            if (l1.isPositiveOrZero && l2.isPositiveNonZero)
            {
                VeryLong q, r;
                q = vlongDivvlong(l1, l2, out r);
                return q;
            }
            else throw new NotImplementedException("op / for positive vlongs");
        }

        public static VeryLong operator %(VeryLong l1, VeryLong l2)
        {
            if (l1.isPositiveOrZero && l2.isPositiveNonZero)
            {
                VeryLong r;
                vlongDivvlong(l1, l2, out r);
                return r;
            }
            else throw new NotImplementedException("op % for positive vlongs");
        }

        public int this[int idx]
        {
            get {
                if (idx >= 0)
                {
                    if (idx < ndgts) return arr[idx];
                    else return 0;
                }
                else throw new IndexOutOfRangeException("VeryLong(get): Index must be positive or zero");
            }
            set {
                if (idx >= 0)
                {
                    if (idx < ndgts) arr[idx]=value;
                    else throw new IndexOutOfRangeException("VeryLong(set): Index exceeds array length");
                }
                else throw new IndexOutOfRangeException("VeryLong(set): Index must be positive or zero");
            }

        }

        #endregion

        #region Test

        /* Test unit

        public void doSome(ref int t, ref VeryLong test)
        {
            t *= t;
            //test = test * test;
            test = test*test;
        }

        public void modThis()
        {
            this.ndgts = 2;
            arr = new int[ndgts];
            arr[0] = 1;
            arr[1] = 1;
        }
        */

        #endregion
    }
}
